KURZUS: Alkalmazott operációkutatás

MODUL: I. modul: Az operációkutatás tárgya és módszerei

2. lecke: Lineáris programozás matematikai modelljei és a normálfeladat megoldása szimplex módszerrel

|  | Tanulási útmutató
| A lineáris programozás numerikus megoldásának módszereit a tankönyv azonos című fejezetében találja meg.
| A módszerek alkalmazása függ a feladat típusától. Ezért fontos, hogy először megismerje a lineáris programozási feladatok típusait.
| Az egyenlőtlenségrendszerben előforduló relációk szerint megkülönböztethetünk normál, módosított normál és általános feladatot. Ezek definíciója és mátrix-vektor szimbólumokkal megadott modelljei a tankönyvben találhatók.
| A szimplex módszer lényegét pedig a tankönyv 1.5. fejezetében találja.
| Tevékenységek
| 2.1. Figyelmesen olvassa el a lineáris programozási feladat definícióját, majd jól jegyezze meg a használt szimbólumokat és azok elnevezését. A tankönyv 1.3. fejezetében találja a lineáris programozási feladatok skalár, majd alatta a vektor-mátrix jelekkel felírt modelljét. Ezeket jól rögzítse, mert az egész tankönyvben ezeket a formákat használjuk.
| 2.2. Olvassa el, és jól jegyezze meg a definíciókat és matematikai szimbólumokkal felírt modellek típusait. A feladatok megoldásakor ezeket kell felismerni, hiszen ettől függően kell alkalmazni a matematikai lépéseket.
| 2.3. Az alkalmazott numerikus módszer (szimplex módszer) lépéseinek leírása és az indoklása a tankönyv 1.5. fejezetében található. A tankönyvben igen tömören van megfogalmazva az eljárás és azok indoklása, ezért többször pontokba foglaltuk az eljárás lényegét. Végeredményben ezt az eljárást kell alkalmazni a megoldás során, de jobban megjegyzi, ha ismeri a matematikai elméletét is.
| 2.4. Igen fontos, hogy a szimplex táblázatban jól eligazodjon. Ez a táblázat sok információt tartalmaz:
| hogyan kell leolvasni a lehetséges megoldást? a lehetséges megoldás optimális-e? alternatív megoldást kapott-e? a célfüggvény korlátos-e?
| Ezen esetek vizsgálatát hasonlítsa össze a grafikus megoldásnál bemutatott esetekkel!
| A bemutatott modelleket oldja meg külön lapon önállóan is. Így meggyőződhet arról, hogy önállóan képes-e megoldani a típusfeladatokat.
| Követelmények
| 2.1. A kulcsszavak kiválasztásával fel tudja írni a lineáris programozási feladatok definícióját.
| 2.2. A különböző módon megadott modellekről el tudja dönteni, hogy milyen típusú lineáris programozási feladatról van szó.
| 2.3. Fel tudja írni egy adott lineáris programozási feladat induló szimplex táblázatát. Bázis transzformációt hibátlanul el tudja végezni, a kapott eredményt le tudja olvasni a szimplex táblázatról.
| 2.4. Egy adott szimplex táblázatról el tudja dönteni, hogy alternatív optimum esetéről van-e szó, vagy a célfüggvény nem korlátos esetéről. Tudni kell, hogy ezekben az esetekben hogyan kell eljárni.

|  | Önellenőrző feladatok
1 | 2 | 3 | 4 | 5 | 6 | 7
elsőfokú | = | ≤ | ≥ | egyenlőtlenségek | nem negatív | nem lineáris
| 1. Fogalmazza meg az alábbi modellek lényegét a felsorolt kulcsszavak kiegészítésével! A szavak feletti számot írja be a megfelelő mezőbe! 1/a Normál feladatnak nevezünk egy maximum feladatot akkor, ha egyenlőtlenségei értelműek és b ¯ 0 ¯ feltétel is teljesül. 1/b Módosított normálfeladatnak nevezünk egy modellt, ha egyenlőtlenségei értelműek, tartalmaz -t és a jobb oldalon b ¯ 0 ¯ feltétel is teljesül. 1/c Általános feladatnak nevezünk egy lineáris modellt, ha feltételei között a b ¯ 0 ¯ fennáll és reláció is szerepel az egyenlőtlenségben. 1/d Olyan feladatot nevezünk lineáris programozási feladatnak, amelyekben a feltételek egyenletek és , a célfüggvényük is és a bennük szereplő váltózók számértéket vehetnek fel.
| 2. Milyen típusú feladatok az alábbi modellek?
1. | x ¯ ≥ 0 ¯ A 1 x ¯ ≤ b ¯ 1 A 2 x ¯ = b ¯ 2 z= c ¯ T ⋅ x ¯ → max⁡ | 2. | x ¯ ≥ 0 ¯ A x ¯ ≤ b ¯ z= c ¯ T ⋅ x ¯ → max⁡
3. | x ¯ ≥ 0 ¯ A x ¯ ≥ b ¯ z= c ¯ T ⋅ x ¯ → min⁡ | 4. | A 1 ⋅ x ¯ ≤ b ¯ 1 A 2 ⋅ x ¯ ≥ b ¯ 2 z= c ¯ T ⋅ x ¯ → min⁡
| Párosítsa az alábbi feladatokat az állításokkal! Írja be a modell számát a megfelelő mezőbe! Ahol nincs megoldás, oda írjon "-" jelet! Normál maximum feladat: Normál minimum feladat: Módosított maximum feladat: Általános maximum feladat: Általános minimum feladat:
| 3. Milyen típusú lineáris programozási feladatok az alábbi modellek?
1. | x 1 , x 2 , x 3 ≥ 0 2 x 1 +5 x 2 + x 3 ≥ 50 x 2 + x 3 ≤ 10 z=20 x 1 + x 2 − x 3 → max⁡ | 2. | x 1 , x 2 , x 3 ≥ 0 2 x 1 +5 x 2 + x 3 ≤ 50 x 1 − x 3 = 10 z= x 1 +10 x 2 − x 3 → max⁡
3. | x 1 , x 2 , x 3 ≥ 0 2 x 1 +5 x 2 + x 3 ≥ 50 x 2 + x 3 ≥ 10 z= x 1 +10 x 2 − x 3 → min⁡ | 4. | x 1 , x 2 , x 3 ≥ 0 2 x 1 +5 x 2 + x 3 ≤ 50 x 1 x 2 − x 3 ≤ 10 z= x 1 +10 x 2 − x 3 → max⁡
| Párosítsa az alábbi feladatokat az állításokkal! Írja be a modell számát a megfelelő mezőbe! Ahol nincs megoldás, oda írjon "-" jelet! Normál maximum feladat: Normál minimum feladat: Módosított maximum feladat: Általános maximum feladat: Általános minimum feladat:
| 4. Oldja meg a következő lineáris programozási feladatot szimplex módszerrel!
| x 1 , x 2 , x 3 ≥ 0 x 1 +2 x 2 ≤ 16 x 1 +4 x 2 + x 3 ≤ 20 z=40 x 1 +20 x 2 +10 x 3 → max⁡
| Vegyen elő négyzetrácsos lapot. Helyezze el a modellt a szimplex táblázatba! Legyen ez a B 0 táblázat. Válasszon generáló elemet az első oszlopból. Végezzen bázistranszformációt! Az eredmény a B 1 táblázat. Ellenőrzéshez tegye a következőt:
| 4/a Írja ide a B 1 táblázat utolsó sorának elemeit:
| 4/b Olvasson le egy lehetséges t megoldást a B 1 táblázatból, ha van! Ahol nincs megoldás, oda írjon "-" jelet! x 1 = x 2 = x 3 = z =
| 4/c Írja le az optimális megoldást, ha létezik! Ha nincs megoldás, a mezőkbe írjon "-" jelet! x 1 = x 2 = x 3 = z =
| 5. Egy lineáris programozási feladat megoldása során az alábbi szimplex táblázatot kaptuk:
| Értékelje a táblázatot: A felkínált válaszok közül válassza ki a helyeset! (Több jó válasz is lehet!)
| Leolvasható egy optimális megoldás, amely x 1 =22; x 2 =0; x 3 =11; z = 820.
| Leolvasható egy lehetséges megoldás, amely x 1 =22 x 2 =0 x 3 =11 z=820
| Alternatív optimuma van a feladatnak.
| A célfüggvény nem korlátos, nincs optimális megoldása.
| A feladatnak nincs lehetséges megoldása, tehát optimális megoldása sem.
| Az optimális megoldás: x 1 =22; x 2 =−80; x 3 =11; z = -820.
| A feladat degenerált.